#!/usr/bin/env python
# coding: utf-8


class Fraction:
    """
    inspired by
    >>> from fractions import Fraction
    """
    def __init__(self, p, q):
        if q < 0:
            p, q = -p, -q
        div = gcd(abs(p), abs(q))
        self._num = p / div
        self._den = q / div

    def __repr__(self):
        return "%s/%s" % (self._num, self._den)

    def __str__(self):
        if self._num % self._den == 0:
            return "%s" % (self._num / self._den)
        return "%s/%s" % (self._num, self._den)

    def __add__(self, f):
        p = self._num * f.getDen() + f.getNum() * self._den
        q = self._den * f.getDen()
        return Fraction(p, q)

    def __mul__(self, f):
        p = self._num * f.getNum()
        q = self._den * f.getDen()
        return Fraction(p, q)

    def __sub__(self, f):
        return self + Fraction(-f.getNum(), f.getDen())

    def __div__(self, f):
        return Fraction(self._num * f.getDen(), self._den * f.getNum())

    def __pow__(self, exp):
        return Fraction(self._num ** exp, self._den ** exp)

    def __eq__(self, f):
        return self._num * f.getDen() == f.getNum() * self._den

    def __gt__(self, f):
        d = self - f
        return d.getNum() > 0

    def __lt__(self, f):
        d = self - f
        return d.getNum() < 0

    def __ge__(self, f):
        d = self - f
        return d.getNum() >= 0

    def __le__(self, f):
        d = self - f
        return d.getNum() <= 0

    def getNum(self):
        """
        java love
        """
        return self._num

    def getDen(self):
        """
        love java
        """
        return self._den


def gcd(x, y):
    """
    Non-recursive greatest common divisor calculator
    """
    while y != 0:
        (x, y) = (y, x % y)
    return x


class TuringMachine:
    """
    Turing Machine implementation
    """
    def __init__(self, transitions, null_sym=' '):
        self._tape = []
        self._head = -1
        self._transitions = transitions
        self._state = 0
        self._null = null_sym

    def start(self, w):
        """
        Start the TM on the given input word 'w'
        """
        self._tape = list(w)
        self._head = 0
        self._state = 0

    def step(self):
        """
        Make one step of the TM execution.
        return None if nothing noteworthy happened,
               True if the TM has stopped and accepts input
               False if the TM rejects input word
        """
        if self._state == len(self._transitions):
            return True
        elif self._state == len(self._transitions) + 1:
            return False

        nxt_st, upd_sym, mv = \
            self._transitions[self._state][self._tape[self._head]]

        self._tape[self._head] = upd_sym
        self._state = nxt_st

        if mv in ['R', 'r']:
            self._head += 1
        elif mv in ['L', 'l']:  # and self._state != 0:
            self._head -= 1

        if self._head == 0:
            self._tape.insert(0, self._null)
            self._head += 1
        if self._head >= len(self._tape) - 1:
            self._tape.append(self._null)

        return None  # successfully stepped

    def __str__(self):
        """
        Печать состояния МТ

        [a][a][b][b]..
            ^
            q3

        a3abb
        """
        return ''.join(self._tape[:self._head]) + \
               '{' + str(self._state) + '}' + \
               ''.join(self._tape[self._head:])

    def run(self, w, verbose=False):
        """
        Auto-pilot
        """
        self.start(w)
        res = self.step()
        while res is None:
            if verbose:
                print(self)
            res = self.step()
        return res


ERASER = [{'a': (0, ' ', 'R'),
           'b': (0, ' ', 'R'),
           ' ': (1, ' ', 'r')}]
